import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution131 {

    public static void main(String args[]) {
        Solution131 s = new Solution131();
        System.out.println(s.partition("aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaa"));
    }

    HashMap<Integer, List<List<String>>> mp;
    public List<List<String>> partition(String s) {
        mp = new HashMap<>();
        return dfs(0, s);
    }

    public List<List<String>> dfs(int st, String s) {
        List<List<String>> ret = new ArrayList<>();
        if (st == s.length() - 1) {
            List<String> tret = new ArrayList<>();
            tret.add(s.charAt(st) + "");
            ret.add(tret);
            return ret;
        }
        if(st == s.length()){
            List<String> tret = new ArrayList<>();
            ret.add(tret);
            return ret;
        }

        if(mp.containsKey(st)){
            return mp.get(st);
        }

        for (int i = st + 1; i <= s.length(); i++) {
            if (is(s.substring(st, i))) {
                String l = s.substring(st, i);
                List<List<String>> tret = dfs(i, s);
                for(int j = 0; j < tret.size() ; j ++){
                    List<String> oneRet = new ArrayList<>(tret.get(j));
                    oneRet.add(0, l);
                    ret.add(oneRet);
                }
            }
        }
        mp.put(st, new ArrayList<>(ret));
        return ret;
    }

    public boolean is(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

}
